#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType date;
    struct Node* next;
}Node;
typedef struct Node *LinkList;   //定义LinkList类型为结构体类型

//单链表的整表创建（头插法）
void CreateLinkListT(LinkList *L,int n)
{
    int i=0;
    LinkList p;
    *L=(LinkList)malloc(sizeof(Node));
    (*L)->next=NULL;
    while(i<n)
    {
        p=(LinkList)malloc(sizeof(Node));
        printf("请输入第%d个结点的数据：",i+1);
        scanf("%d",&p->date);
        i++;

        p->next=(*L)->next;
        (*L)->next=p;
    }
}
//单链表的整表创建（尾插法）
void CreateLinkListW(LinkList* L, int n)
{
    LinkList p,r;
    int i;
    *L=(LinkList)malloc(sizeof(Node));
    r=*L;
    for(i=0;i<n;i++)
    {
        p=(LinkList)malloc(sizeof(Node));
        printf("请输入第%d个结点的数据：",i+1);
        scanf("%d",&p->date);

        r->next=p;
        r=p;
    }
    r->next=NULL;
}
//单链表的打印
void print(LinkList* L,int len)
{
    int i;
    LinkList p;
    p=*L;
    printf("此时的单链表数据为：");
    for (i=0;i<len;i++)
    {
        p=p->next;
        printf("%d ",p->date);
    }
}
//单链表的长度
int ListLength(LinkList* L)
{
    int k=0;
    LinkList List;
    List=(*L)->next;
    while(List!=NULL)
    {
        k++;
        List=List->next;
    }
    return k;
}
//单链表的读取(获得链表的第i个数据)
Status ListGet(LinkList L, int i, ElemType* e)
{
    int j;
    LinkList p;                 //声明一个结点p
    j=1;						//计数器
    p=L->next;				//让p指向链表的第一个结点
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    if(!p||j>i)
        return ERROR;
    else
        *e=p->date;			//查找成功，返回结点p的数据
    return OK;
}
//单链表的插入(在第i个结点处插入值为e的数据)
Status ListInsert(LinkList* L, int i, ElemType e)
{
    int j;
    LinkList p,s;
    p=*L;
    j=1;
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    if(!p&&j>i)
        return ERROR;
    s=(LinkList)malloc(sizeof(Node));
    s->date=e;              //将值赋给s->date
    s->next=p->next;
    p->next=s;

    return OK;
}
//单链表的删除(删除第i个结点的数据，并用e返回其值)
Status ListDelete(LinkList* L, int i, ElemType* e)
{
    int j;
    LinkList p, q;
    p=*L;
    j=1;
    while(p->next&&j<i)
    {
        p=p->next;
        j++;
    }
    if(!(p->next)&&j>i)
    {
        return ERROR;
    }
    else
        q=p->next;
    p->next=q->next;
    *e=q->date;
    free(q);
    return OK;
}
//判断链表是否为空
Status IsEmpty(LinkList* L)
{
    LinkList p;
    p=(*L)->next;
    if(p==NULL)
        return OK;
    else
        return ERROR;
}
int ListSearch(LinkList* L,ElemType x)
{
    LinkList p;
    p=(*L)->next;
    int s=0;
    while(p!=NULL)
    {
        s++;
        if(p->date==x)
        {
            return s;
        }
        else
        {
            p=p->next;
        }
    }
    return -1;
}
int main()
{
    LinkList* L;
    //ElemType* e;
    int value;
    int LinkListLength;
    int len;
    int LocationGet, GetValue;
    int x;
    int s;
    printf("请输入链表长度：");
    scanf("%d",&len);
    L=(LinkList*)malloc(sizeof(Node));
    CreateLinkListW(L,len);
    print(L,len);
    printf("\n\n____________________________________________\n\n");
    printf("请输入需要查询的数据: ");
    scanf("%d",&x);
    s=ListSearch(L,x);
    printf("该数据处于位置%d\n",s);
    printf("\n\n____________________________________________\n\n");
    printf("请输入需要获取的数据位置：");
    scanf("%d", &LocationGet);
    if (ListGet(*L, LocationGet, &GetValue))
        printf("第%d个结点的数据是：%d",LocationGet,GetValue);
    printf("\n\n____________________________________________\n\n");
    printf("请输入要插入的结点位置：");
    scanf("%d", &LocationGet);
    printf("请输入要插入的结点数据：");
    scanf("%d", &value);
    ListInsert(L, LocationGet, value);
    LinkListLength=ListLength(L);
    print(L,LinkListLength);
    printf("\n\n____________________________________________\n\n");
    printf("请输入要删除的结点位置：");
    scanf("%d", &LocationGet);
    ListDelete(L,LocationGet,&GetValue);
    LinkListLength=ListLength(L);
    print(L, LinkListLength);
    printf("\n\n____________________________________________\n\n");
    return 0;
}
